Because reference counting-style garbage collection (GC) has a short pause time, and a high affinity for programming languages that do not have garbage collection (such as C), it has been implemented in many programming languages.
In order to implement reference counting-type garbage collection, the appropriate code has to be inserted for an integer counter indicating the number of times each object has been used ((RC+) for increment and (RC−) for decrement). When the counter is lowered to zero by RC−, the object is reclaimed.
The techniques described in the following patent publications are typical prior art examples of reference counting-style garbage collection.
A device has been disclosed in Laid-Open Patent Application No. 2003-50740 in which effective garbage collection is performed by suppressing memory use when the number of times a memory cell is referenced momentarily reaches a high peak value during the operation of an application program. Small bit string counters are provided in each memory cell so that the peak value for the number of times the memory cell is referenced cannot be represented, and the garbage collection device increments or decrements the counter within a range less than or equal to the maximum value expressed by the bit strings by a counter changing unit when pointers are changed to the memory cell by the application program. When a counter reaches zero, the memory cell is released by a cell releasing unit, and a recounting unit checks the number of times each memory cell has been referenced when there is insufficient memory by tracing the pointer chain from the route pointer. A counter resetting unit releases memory cells whose result is zero, and sets the counter of the memory cells whose result is not zero to the number in the check result.
In the prior art technique described above, the RC+/RC− is inserted explicitly at the beginning in a predetermined position in the code. However, more recently, techniques have been proposed, as described in U.S. Pat. No. 7,693,919 and Joisha, P. G., (2008). Principled Approach to Nondeffered Reference-Counting Garbage Collection. VEEE., in which optimization is performed at an intermediate language level without initially inserting RC+/RC−. Here, the RC+/RC− is inserted at the later phase. This makes optimization easier to apply in compilers.
However, when RC+/RC− is inserted in accordance with the technique described in U.S. Pat. No. 7,693,919 and previously mentioned Joisha (2008), 1) an operation has to be performed to render the address of an object NULL after the last use of the object, 2) RC− is required in successor BB (basic blocks) in the case of variables whose life time has been closed in a BB, and 3) a check is required to determine whether or not the address of an object has been rendered NULL using RC−.